package Sort.MergeSort.myTest;

/**归并排序
 * @program: jvm
 * @description
 * @author: tkk fendoukaoziji
 * @create: 2019-05-16 13:50
 **/
public class TestSortMerge {
    public static void main(String[] args) {
        int[] arr={23,67,104,38,46,34,75,84,28};
        show(arr);
        int[] workArr = new int[arr.length];
        mergeSort(arr,workArr,0,arr.length-1);
        show(arr);

    }

    private static void show(int[] arr) {
        for (int i = 0; i < arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    private static void mergeSort(int[] arr, int[] workArr,int start, int end) {
        if(start==end){
            return;
        }else{
            int mid=(start+end)/2;
            mergeSort(arr,workArr,start,mid);
            mergeSort(arr,workArr,mid+1,end);
            mergeData(arr,workArr,start,mid+1,end);

        }
    }

    private static void mergeData(int[] arr,int[] workArr, int start, int higher, int end) {
        int left=start;
        int mid=higher-1;
        int moving=left;
        while(start<=mid&&higher<=end){
            if(arr[start]<arr[higher]){
                workArr[moving++]=arr[start++];
            }else{
                workArr[moving++]=arr[higher++];
            }
        }
        while(start<=mid){
            workArr[moving++]=arr[start++];
        }
        while(higher<=end){
            workArr[moving++]=arr[higher++];
        }
        for (moving=left ; moving <= end; moving++) {
            arr[moving]=workArr[moving];
        }
    }


}
